import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;

public class Test {
}
class Solution {
    private static final int MOD = (int)1e9 + 7;
    public int numFactoredBinaryTrees(int[] arr) {
        Arrays.sort(arr);
        long sum = 0;
        int n = arr.length;
        long[] dp = new long[n];
        for(int i=0; i<n; i++){
            dp[i] = 1;
            for(int left=0,right=i-1; left<=right; left++){
                while(left<=right && (long)arr[left]*arr[right]>arr[i]){
                    right--;
                }
                if(left<=right && (long)arr[left]*arr[right]==arr[i]){
                    if(right != left){
                        dp[i] = (dp[i] + 2*dp[left]*dp[right])%MOD;
                    }else{
                        dp[i] = (dp[i] + dp[left]*dp[right])%MOD;
                    }
                }
            }
            sum = (sum+dp[i])%MOD;
        }
        return (int)sum;
    }
}
class Solution {
    public int numFactoredBinaryTrees(int[] arr) {
        final long MOD = (long)1e9+7;
        Arrays.sort(arr);
        int n = arr.length;
        Map<Integer,Integer> map = new HashMap<>(n);
        for(int i=0; i<n; i++){
            map.put(arr[i],i);
        }
        long[] memo = new long[n];
        Arrays.fill(memo,-1);
        long ans = 0;
        for(int i=0; i<n; i++){
            ans += dfs(i,arr,memo,map);
        }
        return (int)(ans%MOD);
    }
    long dfs(int i, int[] arr, long[] memo, Map<Integer,Integer> map){
        if(memo[i] != -1) return memo[i];
        int val = arr[i];
        long ans = 1;
        for(int j=0; j<i; j++){
            int x = arr[j];
            if(val%x == 0 && map.containsKey(val/x)){
                ans += dfs(j,arr,memo,map)*dfs(map.get(val/x),arr,memo,map);
            }
        }
        return memo[i]=ans;
    }
}
class Solution {
    public int numFactoredBinaryTrees(int[] arr) {
        final long MOD = (long)1e9+7;
        Arrays.sort(arr);
        int n = arr.length;
        Map<Integer,Integer> map = new HashMap<>(n);
        for(int i=0; i<n; i++){
            map.put(arr[i],i);
        }
        long[] f = new long[n];
        long ans = 0;
        for(int i=0; i<n; i++){
            int val = arr[i];
            f[i] = 1;
            for(int j=0; j<i; j++){
                int x = arr[j];
                if(val%x==0 && map.containsKey(val/x)){
                    f[i] += f[j]*f[map.get(val/x)];
                }
            }
            ans += f[i];
        }
        return (int)(ans%MOD);
    }
}